// https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/

// 算法思路总结：
// 1. 广度优先搜索实现N叉树的层序遍历
// 2. 使用队列辅助，按层处理节点
// 3. 每层开始时记录当前队列大小，确保同层节点一起处理
// 4. 遍历每个节点的所有子节点并入队
// 5. 使用move语义优化vector拷贝性能
// 6. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <queue>
#include <vector>
#include <algorithm>

class Node
{
public:
    int val;
    vector<Node*> children;

    Node() {}
    Node(int _val)
    {
        val = _val;
    }
    Node(int _val, vector<Node*> _children)
    {
        val = _val;
        children = _children;
    }
};

Node* buildTree(const vector<string>& nodes) 
{
    if (nodes.empty() || nodes[0] == "null") return nullptr;
    
    Node* root = new Node(stoi(nodes[0]));
    queue<Node*> q;
    q.push(root);
    int i = 2;  
    
    while (!q.empty() && i < nodes.size()) 
    {
        Node* current = q.front();
        q.pop();
        
        vector<Node*> children;

        while (i < nodes.size() && nodes[i] != "null") 
        {
            Node* child = new Node(stoi(nodes[i]));
            children.push_back(child);
            q.push(child);
            i++;
        }
        current->children = children;
        
        if (i < nodes.size() && nodes[i] == "null") 
        {
            i++;
        }
    }
    
    return root;
}

void printResult(const vector<vector<int>>& result) 
{
    cout << "[";
    for (int i = 0; i < result.size(); ++i) 
    {
        cout << "[";
        for (int j = 0; j < result[i].size(); ++j) 
        {
            cout << result[i][j];
            if (j < result[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

class Solution 
{
public:
    vector<vector<int>> levelOrder(Node* root) 
    {
        if (root == nullptr) return {};

        vector<vector<int>> ret;
        queue<Node*> q;
        q.push(root);

        while (!q.empty())
        {
            int sz = q.size();
            vector<int> level;
            for (int i = 0 ; i < sz ; i++)
            {
                Node* node = q.front();
                q.pop();
                level.push_back(node->val);
                for (auto& childnode : node->children)
                    if (childnode != nullptr)
                        q.push(childnode);
            }
            ret.push_back(move(level));
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<string> nodes1 = {"1", "null", "3", "2", "4", "null", "5", "6"};
    vector<string> nodes2 = {"1", "null", "2", "3", "4", "5", "null", "null", "6", "7", "null", "8", "null", "9", "10", "null", "null", "11", "null", "12", "null", "13", "null", "null", "14"};

    Node* root1 = buildTree(nodes1);
    Node* root2 = buildTree(nodes2);

    vector<vector<int>> result1 = sol.levelOrder(root1);
    vector<vector<int>> result2 = sol.levelOrder(root2);

    printResult(result1);  
    printResult(result2);  

    return 0;
}